#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File        :   142. 环形链表 II.py
@Contact     :   lhouctcs@163.com
@License     :   MIT
@Time        :   2023/2/4 14:36
@Author      :   lhou 
@Version     :   0.1.0
@Description :
"""
from typing import Optional


# import lib
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 如果相遇
            if slow == fast:
                p = head
                q = slow
                while p != q:
                    p = p.next
                    q = q.next
                # 你也可以return q
                return p

        return None
